package com.atguigu.practice;

import java.util.Scanner;

public class TheSpacePassword {
    public static void main(String[] args) {
        int nums[]=new int[10001];
        nums[1]=1;
        nums[2]=2;
        for(int i=3;i<10001;i++){
            nums[i]=nums[i-1]+nums[i-2];
            nums[i]=nums[i]%10000;
        }
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNext()){
            int n=scanner.nextInt();
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<n;i++){
                int xi=scanner.nextInt();
                sb.append(String.format("%04d",nums[xi]));
            }
            System.out.println(sb);
        }
    }
}
